Negascout

Negascout es una variante del algoritmo Minimax, es un algoritmo que combina la relación matemática del Negamax y el uso de ventana nula.

También llamado "búsqueda de la variante principal" este algoritmo puede ofrecer rendimientos incluso mayores a la poda alfa-beta si los nodos se encuentran correctamente ordenados.

Al igual que alfa-beta, negascout es un algoritmo de búsqueda direccional para calcular el valor minimax de un nodo en un árbol. La mejora del algoritmo negascout sobre el algoritmo alfa-beta es que el primero no examinará un nodo que el segundo podaría.

Este algoritmo es útil siempre y cuando los nodos estén bien ordenados ya que supone que el primer nodo explorado será el mejor, así podrá confirmarlo en otros nodos usando la ventana nula. En caso de fallo, como el primer nodo no era el de máximo nivel, se seguirá buscando el mejor nodo en el árbol del mismo modo que en el algoritmo alfa-beta.

pseudocodigo:

int negascout(nodo, profundidad, α, β) {
    if (esTerminal(nodo) || profundidad==0)
        return valorHeuristico(nodo);
    b = β;  // la ventana inicial es (-β, -α)
    foreach nodoHijo
        a = -negascout (hijo, profundidad-1, -b, -α);
        if (a>α) α = a;
        if (α>=β)
            return α; //Corte Beta
        if (α>=b)  //comprueba si fallo la ventana nula
           α = -negascout(hijo, profundidad-1, -β, -α);  //Nueva búsqueda completa
           if (α>=β)
               return α; //Corte Beta    
        b = α+1; //Crea nuava ventana nula             
    return α;
}